package 栈与队列;

import java.util.Stack;

/**
 * 129. 求根节点到叶节点数字之和
 *
 * 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
 * 每条从根节点到叶节点的路径都代表一个数字：
 *
 * 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
 * 计算从根节点到叶节点生成的 所有数字之和 。
 *
 * 叶节点 是指没有子节点的节点。
 *
 * 思路： 要统计出从根节点到叶子节点的路径，可以使用DFS深度优先搜索遍历。
 *  通过dfs遍历，将左右子树之和结果相加作为当前子树的总和。
 *
 * 解题步骤：
 * 1：递归思路：
 *   从根节点开始，维护一个当前路径的累积值currentSum
 *   对于每个节点，更新累积值currentSum = currentSum * 10 + node.val
 *   如果当前节点时叶子节点，则直接返回累积值；
 *   否则，递归遍历左右子树，并将左右子树的结果相加作为当前子树的总和。
 * 2：终止条件：
 *   当前节点为null时，返回0；
 *   当前节点时叶子节点时，返回计算后的累积值，
 */
public class L_129 {


    public int sumNumbers(TreeNode root) {
       if(root == null){
           return 0;
       }
         return dfs(root, 0);
    }

    private int dfs (TreeNode root, int currentSum){
        if(root == null){
            return 0; //空节点不贡献值
        }
        // 更新当前路径的累积值
        currentSum = currentSum * 10 + root.val;
        // 如果当前节点是叶子节点，则返回累积值
        if(root.left == null && root.right == null){
            return currentSum;
        }
        return dfs(root.left, currentSum) + dfs(root.right, currentSum);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
